Computational Complexity
------------------------

<!--
SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.

SPDX-License-Identifier: CC0-1.0
-->

[(Up)](../../README.md#topics) | _See also: [Theory of Computation](../Theory%20of%20Computation/README.md#theory-of-computation)_

- - - -


### Web resources

[Computability and Complexity (Stanford Encyclopedia of Philosophy)](https://plato.stanford.edu/entries/computability/) ★★★

[Descriptive Complexity](https://people.cs.umass.edu/~immerman/descriptive_complexity.html) ★★

[Examples of collapsing hierarchies](https://cstheory.stackexchange.com/questions/47333/examples-of-collapsing-hierarchies) ★

[Law of the Excluded Middle in complexity theory](https://cstheory.stackexchange.com/questions/53305/law-of-the-excluded-middle-in-complexity-theory) ★

[Galactic algorithm - Wikipedia](https://en.wikipedia.org/wiki/Galactic_algorithm)

[Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science](http://theoryofcomputing.org/) ★ [💭](commentary/cpressey.md#theory-of-computing-an-open-access-electronic-journal-in-theoretical-computer-science)

### P, NP, and beyond

[Do I need to consider instance restrictions when showing a language is in P?](https://cs.stackexchange.com/questions/105692/do-i-need-to-consider-instance-restrictions-when-showing-a-language-is-in-p) ★

[Cobham\'s thesis - Wikipedia](https://en.wikipedia.org/wiki/Cobham's_thesis)

[Are there any computational problems in groups that are harder than P?](https://mathoverflow.net/questions/321547/are-there-any-computational-problems-in-groups-that-are-harder-than-p) ★

[Subexponentially solvable hard graph problems](https://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems)

[A category of NP-complete problems?](https://cstheory.stackexchange.com/questions/3074/a-category-of-np-complete-problems)

### P versus NP

[P-versus-NP page](https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm) ★

[Computational Complexity: So You Think You Settled P verus NP](http://blog.computationalcomplexity.org/2009/01/so-you-think-you-settled-p-verus-np.html) ★★★

[About P=NP and SAT « Gödel's Lost Letter and P=NP](http://rjlipton.wordpress.com/about/) ★

### PSPACE

[Computational Complexity: A Simple PSPACE-Complete Problem](https://blog.computationalcomplexity.org/2012/11/a-simple-pspace-complete-problem.html) ★★★

### PR

[Inverse Ackermann - primitive recursive or not?](https://mathoverflow.net/questions/76037/inverse-ackermann-primitive-recursive-or-not) ★

[Between mu- and primitive recursion](http://mathoverflow.net/questions/46350/between-mu-and-primitive-recursion) ★

[Is the collection of primitive recursive functions a lower set in the poset of computable functions?](https://mathoverflow.net/questions/364494/is-the-collection-of-primitive-recursive-functions-a-lower-set-in-the-poset-of-c)


### Papers

Why Philosophers Should Care About Computational Complexity (online @ [www.scottaaronson.com](https://www.scottaaronson.com/papers/philos.pdf), [arxiv.org](https://arxiv.org/abs/1108.1791v3)) ★★★ [💭](commentary/cpressey.md#why-philosophers-should-care-about-computational-complexity)

Protein folding is NP-hard (online @ [www.gwern.net](https://www.gwern.net/docs/1993-fraenkel.pdf)) ★

Complexity Hierarchies Beyond Elementary (online @ [arxiv.org](https://arxiv.org/abs/1312.5686)) [💭](commentary/cpressey.md#complexity-hierarchies-beyond-elementary)

The Typed Lambda Calculus is not Elementary Recursive (online @ [www.cs.cornell.edu](https://www.cs.cornell.edu/courses/cs6110/2012sp/Statman-typed-lambda-calculus.pdf)) ★

Pure vs Impure Lisp (online @ [dl.acm.org](https://dl.acm.org/doi/pdf/10.1145/244795.244798))

_(in [Modal Logic](../Modal%20Logic/README.md#modal-logic))_ Topology, Connectedness, and Modal Logic (online @ [www.dcs.bbk.ac.uk](https://www.dcs.bbk.ac.uk/~roman/papers/aiml-08-55.pdf), [web.archive.org](https://web.archive.org/web/20240413205519/https://www.dcs.bbk.ac.uk/~michael/AiML-08.pdf)) ★ [💭](commentary/cpressey.md#topology-connectedness-and-modal-logic)

_(in [Model Checking](../Model%20Checking/README.md#model-checking))_ [Model Checking CTL is Almost Always Inherently Sequential](https://arxiv.org/abs/1103.4990) [💭](commentary/cpressey.md#model-checking-ctl-is-almost-always-inherently-sequential)


### Books

Computers and Tractability (borrow with print disabilities @ [archive.org](https://archive.org/details/computersintract0000gare)) 🏛️ [💭](commentary/cpressey.md#computers-and-tractability)

Computational Complexity (Papadimitriou) (borrow with print disabilities @ [archive.org](https://archive.org/details/computationalcom0000papa)) ★ [💭](commentary/cpressey.md#computational-complexity-papadimitriou)

Computational Complexity (Wagner and Wechsung) (borrow with print disabilities @ [archive.org](https://archive.org/details/computationalcom0000wagn)) ★ [💭](commentary/cpressey.md#computational-complexity-wagner-and-wechsung)

_(in [Linguistics](../Linguistics/README.md#linguistics))_ The Language Complexity Game (borrow @ [archive.org](https://archive.org/details/languagecomplexi00rist)) ★ [💭](commentary/cpressey.md#the-language-complexity-game)